class Solution {
public:
    unordered_map<string,vector<pair<string,double> > > graph;
    
    double dfs(unordered_set<string>& visited,string start,string end,double val){
        if(start == end){
            return val;
        }
        visited.insert(start);
        for(auto& node : graph[start]){
            if(!visited.count(node.first)){
               double ret = dfs(visited,node.first,end,val * node.second);
                if(ret > 0){
                    return ret;
                }
            }
        }
        return -1.0;
    }
    
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        for(int i = 0;i < equations.size();i++){
            graph[equations[i][0]].push_back({equations[i][1],values[i]});
            graph[equations[i][1]].push_back({equations[i][0],1 / values[i]});
        }
        
        vector<double> ret(queries.size(),-1.0);
        for(int i = 0;i < queries.size();i++){
            if(graph.count(queries[i][0]) && graph.count(queries[i][1])){
                unordered_set<string> visited;
                ret[i] = dfs(visited,queries[i][0],queries[i][1],1);
            }
        }
        return ret;
    }
};
